839. Пересечение отрезков

 

Два отрезка на плоскости заданы целочисленными координатами своих концов в декартовой системе координат.

 

Определите, существует ли у них общая точка.

 

Вход. В первой строке содержатся координаты первого конца первого отрезка, во второй – второго конца первого отрезка, в третьей и четвёртой – координаты концов второго отрезка. Координаты целые и по модулю не превосходят 10000.

 

Выход. Выведите “Yes”, если отрезки имеют общую точку, и “No” иначе.

 

Пример входа 1

Пример выхода 1

0 0

1 0

1 0

1 1

Yes

 

 

Пример входа 2

Пример выхода 2

0 0

1 0

2 0

3 0

No

 

 

РЕШЕНИЕ

геометрия

 

Анализ алгоритма

Ограничивающим прямоугольником геометрической фигуры называется наименьший из прямоугольников со сторонами, параллельными осям координат, который содержит в себе эту фигуру. Для отрезка с концами (x1, y1) и (x2, y2) ограничивающим будет прямоугольник с левым нижним углом (x1’, y1’) и правым верхним углом (x2’, y2’), где x1’ = min(x1, x2), y1’ = min(y1, y2), x2’ = max(x1, x2), y2’ = max(y1, y2).

 

Отрезки AB и CD пересекаются тогда и только тогда, когда:

1. Пересекаются прямоугольники, которые их ограничивают;

2. [AC ´ AB] * [AD ´ AB] £ 0;

3. [CA ´ CD] * [CB ´ CD] £ 0.

 

Ниже представлены различные случаи взаимного расположения двух отрезков и соответствующие значения векторных произведений:

 

 

 

 

 

 


AC ´ AB < 0, AD ´ AB > 0              AC ´ AB < 0,  AD ´ AB < 0

 

 

 

 

 


AC ´ AB < 0, AD ´ AB = 0              AC ´ AB = 0,  AD ´ AB = 0

 

В следующем примере каждый из отрезков пересекает прямую, содержащую второй отрезок. Но при этом не пересекаются прямоугольники, их ограничивающие.

 

 

 

 

 


Пример

В первом примере отрезки пересекаются. Во втором примере – нет.

 

Реализация алгоритма

Поскольку входные координаты концов отрезка целые, то при вычислениях будем работать только с целочисленным типом long long. В дальнейшем нам необходима будет функция sgn, вычисляющая знак числа n.

 

int sgn(long long n)

{

  return (n > 0) - (n < 0);

}

 

Пусть концы отрезков AB и CD имеют координаты: A(x1,y1), B(x2,y2), C(x3,y3), D(x4,y4). Функция RectanglesIntersects принимает в качестве аргументов 8 координат концов отрезков и выводит 1, если прямоугольники, ограничивающие отрезки AB и CD, пересекаются. Иначе функция возвращает 0.

 

int RectanglesIntersects(long long x1,long long y1,long long x2,

    long long y2,long long x3,long long y3,long long x4,long long y4)

{

  if (sgn(x3 - x2) * sgn(x4 - x1) > 0) return 0;

  if (sgn(y3 - y2) * sgn(y4 - y1) > 0) return 0;

  return 1;

}

 

Функция intersect проверяет, пересекаются ли отрезки AB и CD. Сначала проверяется пересечение ограничивающих прямоугольников. Если они пересекаются, то строятся вектора AC, AB, AD, CA, CB, CD (например, координаты вектора CD содержатся в переменных CDx и CDy) и вычисляются векторные произведения, указанные в пунктах 2 и 3 условия пересечения отрезков. В зависимости от значений векторных произведений формируется возвращаемое значение. Оно равно 1, если отрезки AB и CD пересекаются и 0 иначе.

 

int intersect(long long x1,long long y1,long long x2,long long y2,

              long long x3,long long y3,long long x4,long long y4)

{

  long long ABx, ABy, ACx, ACy, ADx, ADy;

  long long CAx, CAy, CBx, CBy, CDx, CDy;

  long long ACxAB, ADxAB, CAxCD, CBxCD;

  if (!RectanglesIntersects(min(x1,x2),min(y1,y2),max(x1,x2),

      max(y1,y2),min(x3,x4),min(y3,y4),max(x3,x4),max(y3,y4)))

    return 0;

 

  ACx = x3 - x1; ACy = y3 - y1;

  ABx = x2 - x1; ABy = y2 - y1;

  ADx = x4 - x1; ADy = y4 - y1;

 

  CAx = x1 - x3; CAy = y1 - y3;

  CBx = x2 - x3; CBy = y2 - y3;

  CDx = x4 - x3; CDy = y4 - y3;

 

  ACxAB = ACx * ABy - ACy * ABx;

  ADxAB = ADx * ABy - ADy * ABx;

  CAxCD = CAx * CDy - CAy * CDx;

  CBxCD = CBx * CDy - CBy * CDx;

 

Во избежание переполнения следует сравнивать с нулем не произведение чисел, а произведение их знаков.

 

  if ((sgn(ACxAB) * sgn(ADxAB) > 0) || (sgn(CAxCD) * sgn(CBxCD) > 0))

    return 0;

  return 1;

}

 

Основная часть программы. Читаем входные данные.

 

scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2);

scanf("%lld %lld %lld %lld",&x3,&y3,&x4,&y4);

 

Проверяем пересечение отрезков.

 

if (intersect(x1,y1,x2,y2,x3,y3,x4,y4)) printf("Yes\n");

else printf("No\n");